//12.整数转罗马数字
//https://leetcode.cn/problems/integer-to-roman
class Solution {
public:
    string intToRoman(int num) {
        const pair<int, const char*> arr[] = { {1000,"M"},{900,"CM"},{500,"D"},{400,"CD"},
        {100,"C"},{90,"XC"},{50,"L"},{40,"XL"},{10,"X"},{9,"IX"},
        {5,"V"},{4,"IV"},{1,"I"} };

        string ret;
        int pos = 0;
        while (num)
        {
            while (num >= arr[pos].first)
            {
                ret += arr[pos].second;
                num -= arr[pos].first;
            }
            if (num < arr[pos].first) ++pos;
        }
        return ret;
    }
};
